SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Programming complexity</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Programming complexity</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a>.</div><p><b>Programming complexity</b> (or <b>software complexity</b>) is a term that includes software properties that affect internal interactions. Several commentators distinguish between the terms "complex" and "complicated". Complicated implies being difficult to understand, but ultimately knowable. Complex, by contrast, describes the interactions between entities. As the number of entities increases, the number of interactions between them increases exponentially, making it impossible to know and understand them all. Similarly, higher levels of complexity in software increase the risk of unintentionally interfering with interactions, thus increasing the risk of introducing defects when changing the software. In more extreme cases, it can make modifying the software virtually impossible.

</p><p>The idea of linking software complexity to software maintainability has been explored extensively by <a href="Meir_M._Lehman" class="mw-redirect" title="Meir M. Lehman">Professor Manny Lehman</a>, who developed his <a href="Lehman's_laws_of_software_evolution" title="Lehman's laws of software evolution">Laws of Software Evolution</a>. He and his co-author <a href="Les_Belady" class="mw-redirect" title="Les Belady">Les Belady</a> explored numerous <a href="Software_metrics" class="mw-redirect" title="Software metrics">software metrics</a> that could be used to measure the state of software, eventually concluding that the only practical solution is to use deterministic complexity models.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Types">Types</h2></div>

<p>The complexity of an existing program determines the complexity of changing the program. Problem complexity can be divided into two categories:<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<ol><li><b>Accidental complexity</b> relates to difficulties a programmer faces due to the software engineering tools. Selecting a better tool set or a higher-level programming language may reduce it. Accidental complexity often results from not using the domain to frame the form of the solution. <a href="Domain-driven_design" title="Domain-driven design">Domain-driven design</a> can help minimize accidental complexity.</li>

<li><b>Essential complexity</b> is caused by the characteristics of the problem to be solved and cannot be reduced.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Measures">Measures</h2></div>

<p>Several measures of software complexity have been proposed. Many of these, although yielding a good representation of complexity, do not lend themselves to easy measurement. Some of the more commonly used metrics are

</p>

<ul><li><a href="Cyclomatic_complexity" title="Cyclomatic complexity">McCabe's cyclomatic complexity metric</a></li>

<li><a href="Halstead_complexity_measures" title="Halstead complexity measures">Halstead's software science metrics</a></li>

<li>Henry and Kafura introduced "Software Structure Metrics Based on Information Flow" in 1981,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> which measures complexity as a function of "fan-in" and "fan-out". They define fan-in of a procedure as the number of local flows into that procedure plus the number of data structures from which that procedure retrieves information. Fan-out is defined as the number of local flows out of that procedure plus the number of data structures that the procedure updates. Local flows relate to data passed to, and from procedures that call or are called by, the procedure in question. Henry and Kafura's complexity value is defined as "the procedure length multiplied by the square of fan-in multiplied by fan-out" (Length ×(fan-in × fan-out)²).</li>

<li>Chidamber and Kemerer introduced "A Metrics Suite for Object-Oriented Design" in 1994,<sup id="cite_ref-:0_4-0" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> focusing on metrics for object-oriented code. They introduce six OO complexity metrics: (1) weighted methods per class; (2) coupling between object classes; (3) response for a class; (4) number of children; (5) depth of inheritance tree; and (6) lack of cohesion of methods.</li></ul>

<p>Several other metrics can be used to measure programming complexity:

</p>

<ul><li>Branching complexity (Sneed Metric)</li>

<li>Data access complexity (Card Metric)</li>

<li>Data complexity (Chapin Metric)</li>

<li>Data flow complexity (Elshof Metric)</li>

<li>Decisional complexity (McClure Metric)</li>

<li>Path Complexity (Bang Metric)</li></ul>

<p><a href="Law_of_conservation_of_complexity" title="Law of conservation of complexity">Tesler's Law</a> is an <a href="Adage" class="mw-redirect" title="Adage">adage</a> in <a href="Human%E2%80%93computer_interaction" title="Human–computer interaction">human–computer interaction</a> stating that every <a href="Application_software" title="Application software">application</a> has an inherent amount of complexity that cannot be removed or hidden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Chidamber_and_Kemerer_Metrics">Chidamber and Kemerer Metrics</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>Chidamber and Kemerer<sup id="cite_ref-:0_4-1" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> proposed a set of programing complexity metrics widely used in measurements and academic articles: weighted methods per class, coupling between object classes, response for a class, number of children, depth of inheritance tree, and lack of cohesion of methods, described below:

</p>

<ul><li>Weighted methods per class ("WMC")

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle WMC=\sum _{i=1}^{n}c_{i}}</annotation>

</semantics>

</math></span><img src="./c70465f8e5dccf1eddd9db25170e582a1ee7cfbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.291ex; height:6.843ex;" alt="{\displaystyle WMC=\sum _{i=1}^{n}c_{i}}" loading="lazy"></span></li>

<li>n is the number of methods on the class</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation>

</semantics>

</math></span><img src="./01acb7953ba52c2aa44264b5d0f8fd223aa178a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}" loading="lazy"></span> is the complexity of the method</li></ul></li>

<li>Coupling between object classes ("CBO")

<ul><li>number of other class which is coupled (using or being used)</li></ul></li>

<li>Response for a class ("RFC")

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RFC=|RS|}</annotation>

</semantics>

</math></span><img src="./7c8d87bf5b079102b52b6fb787350738abd30ec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.926ex; height:2.843ex;" alt="{\displaystyle RFC=|RS|}" loading="lazy"></span> where</li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle RS=\{M\}\cup _{all\ i}\{R_{i}\}}</annotation>

</semantics>

</math></span><img src="./59dd88e130aaee093af8e6ae0e2b75727da3ef2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.83ex; height:2.843ex;" alt="{\displaystyle RS=\{M\}\cup _{all\ i}\{R_{i}\}}" loading="lazy"></span></li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{i}}</annotation>

</semantics>

</math></span><img src="./db421291be9d0103404ced7495b363437b67b6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle R_{i}}" loading="lazy"></span> is set of methods called by method i</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> is the set of methods in the class</li></ul></li>

<li>Number of children ("NOC")

<ul><li>sum of all classes that inherit this class or a descendant of it</li></ul></li>

<li>Depth of inheritance tree ("DIT")

<ul><li>maximum depth of the inheritance tree for this class</li></ul></li>

<li>Lack of cohesion of methods ("LCOM")

<ul><li>Measures the intersection of the attributes used in common by the class methods</li>

<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle LCOM={\begin{cases}|P|-|Q|,&{\text{if }}|P|>|Q|\\0,&{\text{otherwise }}\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle LCOM={\begin{cases}|P|-|Q|,&{\text{if }}|P|>|Q|\\0,&{\text{otherwise }}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./05f8492a298a550deeb8971f6c9859a5b680dd9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.348ex; height:6.176ex;" alt="{\displaystyle LCOM={\begin{cases}|P|-|Q|,&{\text{if }}|P|>|Q|\\0,&{\text{otherwise }}\end{cases}}}" loading="lazy"></span></li>

<li>Where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\{(I_{i},I_{j})|I_{i}\cap I_{j}=\emptyset \}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\{(I_{i},I_{j})|I_{i}\cap I_{j}=\emptyset \}}</annotation>

</semantics>

</math></span><img src="./f6e56064f36673758601ec3b8851b936954cfa18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.014ex; height:3.009ex;" alt="{\displaystyle P=\{(I_{i},I_{j})|I_{i}\cap I_{j}=\emptyset \}}" loading="lazy"></span></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=\{(I_{i},I_{j})|I_{i}\cap I_{j}\neq \emptyset \}}</annotation>

</semantics>

</math></span><img src="./3afa0213cb3ab16d91f897c4529fd2cdb3b6c56d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.106ex; height:3.009ex;" alt="{\displaystyle Q=\{(I_{i},I_{j})|I_{i}\cap I_{j}\neq \emptyset \}}" loading="lazy"></span></li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{i}}</annotation>

</semantics>

</math></span><img src="./d896cad5ad71ce7719175ca29d4d109333d4c320.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.823ex; height:2.509ex;" alt="{\displaystyle I_{i}}" loading="lazy"></span> is the set of attributes (instance variables) accessed (read from or written to) by the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-th method of the class</li></ul></li></ul>

<ul><li><a href="Programming_paradigm" title="Programming paradigm">Programming paradigm</a></li>

<li><a href="Software_crisis" title="Software crisis">Software crisis</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">MM Lehmam LA Belady; Program Evolution - Processes of Software Change 1985</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://academia.edu.documents.s3.amazonaws.com/1811257/SHSM2011.pdf">In software engineering, a problem can be divided into its accidental and essential complexity [1].</a></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Henry, S.; Kafura, D. IEEE Transactions on Software Engineering Volume SE-7, Issue 5, Sept. 1981 Page(s): 510 - 518</span>

</li>

<li id="cite_note-:0-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Chidamber, S.R.; Kemerer, C.F. IEEE Transactions on Software Engineering Volume 20, Issue 6, Jun 1994 Page(s):476 - 493</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Programming_complexity&oldid=1296686654">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>